7,[2,3,5,4,5,5],[5,2,1,6,7,4],[15,6,14,4,1,6]
35
当牛牛和牛妹分别被分到 , 两个房子时,路径最长。
房子 , 房子 , 街道长度 。表示房子 与房子 之间有一条长度为 的道路相连。。
import collections class Solution: def solve(self, n, u, v, w): # write code here edges = collections.defaultdict(list) dis = {} k = len(u) for i in range(k): edges[u[i] - 1].append(v[i] - 1) edges[v[i] - 1].append(u[i] - 1) dis[(v[i] - 1, u[i] - 1)] = w[i] dis[(u[i] - 1, v[i] - 1)] = w[i] node, d = -1, 0 def dfs(cur_node, cur_dis, visited): nonlocal node, d, edges if cur_dis > d: node = cur_node d = cur_dis for next_ in edges[cur_node]: if next_ not in visited: visited.append(next_) dfs(next_, cur_dis + dis[(cur_node, next_)], visited) return dfs(0,0,[0]) dfs(node,0,[node]) return d